package tree;


import java.util.ArrayList;
import java.util.List;


public class LexicographicalOrder {
    /**
     * 力扣 386. 字典序排数
     * 给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
     *
     * 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
     *
     * 字典序
     *
     *
     * */
    //迭代处理
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        //j作为当前轮到的数字
        for(int i = 0,j = 1;i < n;i ++) {
            //直接加进去
            res.add(j);
            //根据字典序，前缀相同时比从不相同开始比较
            if(j * 10 <= n) {
                //找到最大的最后一位为0的
                j *= 10;
            }else {
                //当最后一位为9表示当前这颗子树结束了，或者当前数大于n，开始下一颗子树
                while(j % 10 == 9 || j + 1 > n) {
                    j /= 10;
                }
                j ++;
            }
        }
        return res;
    }

    //递归处理
    List<Integer> res2;
    public List<Integer> lexicalOrder2(int n) {
        res2 = new ArrayList<>();
        //0不算
        for(int i = 1;i <= 9;i ++) {
            dfs(i,n);
        }
        return res2;
    }
    public void dfs(int t,int n) {
        //大于就结束
        if(t > n) return;
        res2.add(t);
        //处理0不算之外10,100,这些包含0的都要算进去
        for(int i = 0;i < 10;i ++) {
            dfs(t * 10 + i,n);
        }
    }


}
